package review.Day_0406;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zxc
 * @date 2023/04/06 15:03
 **/
public class Solution01 {
    /**
     * 思考 ：若是元素是后入先出的话（类似于栈Stack），则可以使用辅助栈来记录 存储数量不一致的元素时的最大元素;
     * ===>
     * 进一步思考 ：若是元素是先入先出的话（类似于队列queue），则如何去记录 该队列中所有元素的最大值呢？
     * 答 ：维护一个单调双端队列
     * 1.每次向队列队尾中插入元素的话，都是需要判断 所维护单调双端队列的队尾元素是否大于所要插入的元素;
     * （1）所维护单调双端队列的队尾元素 >= 所要插入的元素的情况下，则直接将所要插入元素添加到单调双端队列中;
     * （2）所维护单调双端队列的队尾元素 < 所要插入的元素的情况下，
     *  则删除所维护单调双端队列的队尾元素，直至其队尾元素 >= 所要插入元素，再将所要插入元素添加到单调双端队列中;
     * 2.每次从队列中删除队首元素时，则需要去判断 所删除的元素是否与单调双端队列的队首元素相等；
     * （1）所要删除的队首元素 == 单调双端队列的队首元素的情况下，
     *  则不仅仅要删除队列中的队首元素，同时还需要删除所维护的单调双端队列的队首元素;
     * （2）所要删除的队首元素 < 单调双端队列的队首元素的情况下，则直接伤处队列中的队首元素即可;
     * ===>
     * 因此，所维护的双端队列中所存储的元素是严格符合单调递减结构的;
     *
     */
    // 存储元素的队列
    Queue<Integer> queue;
    // 所维护的单调双端队列
    Deque<Integer> deque;
    // 初始化操作 ：
    public Solution01() {
        queue = new LinkedList<>();
        deque = new LinkedList<>();
    }
    // 返回此时队列中的最大元素 ：
    public int max_value() {
        // 队列为空的情况 ：
        if(deque.isEmpty()){
            return -1;
        }
        // 直接返回所维护的单调双端队列队首元素即可;
        return deque.peekFirst();
    }
    // 向队列尾部添加元素 ：
    public void push_back(int value) {
        // 向队列尾部添加元素
        queue.offer(value);
        // 同时，对于所维护的单调双端队列进行更新
        while(!deque.isEmpty() && deque.peekLast() < value){
            // 双端队列不为空 && 双端队列的队尾元素 < 所要插入元素
            // 则删除所维护的双端队列的队尾元素;
            deque.pollLast();
        }
        // 所添加的元素，是必然需要加入到所维护的双端队列deque中的;
        deque.offer(value);
    }
    // 删除队列头部元素 ：
    public int pop_front() {
        // 队列为空的情况 ：
        if(queue.isEmpty()){
            return -1;
        }
        /**
         * 注意 ：Integer是基本类型int的包装类;
         * ===》
         * （1）即，Integer对象值在[-128，127]范围内时，所使用的Integer对象是 Integer类所维护的缓存中的Integer对象;
         * （2）若是Integer对象值不在上述范围内的话，则会重新构建一个Integer对象;
         *
         */
        Integer pollValue = queue.poll();
        // 所删除的队首元素 == 所维护双端队列的队首元素的情况下 ：
        if(pollValue.equals(deque.peek())){
            // 删除所维护双端队列的队首元素;
            deque.poll();
        }
        return pollValue;
    }
}
